10006 - Carmichael numbers/p10006.cpp

   1 #include <iostream>
   2 #include <stdio.h>
   3 #include <string>
   4 using namespace std;
   5
   6 const int MAX = 65001;
   7
   8 //p[x] == 0 si x es primo, sino p[x] == 1
   9 int p[MAX];
  10
  11 //pot[i] contiene (a^(2^i))mod(n)
  12 long long pot[16];
  13
  14 //f retorna (a^n)mod(n). Solo funciona si a,n < 65000!
  15 //corre en orden O(log_2(n))
  16 long long f(long long a, long long n){
  17   string bin="";
  18   long long  r;
  19   long long temp = n;
  20   while (temp > 0){
  21     r = temp % 2;
  22     temp = temp / 2;
  23     bin = (char)('0'+r) + bin;
  24   }
  25
  26   pot[0] = a % n;
  27   for (int i=1; i<16; ++i){
  28     pot[i] = (pot[i-1]*pot[i-1]) % n;
  29   }
  30
  31   r=1;
  32   for (int i=0; i<bin.size(); ++i){
  33     if (bin[i] == '1'){
  34       r = (r * pot[bin.size()-i-1]) % n;
  35     }
  36   }
  37   return r;
  38 }
  39
  40
  41 bool c(int n){
  42   for (int a=2; a<n; ++a){
  43     //si no lo pasa return false
  44     long long r = f(a,n);
  45     if (r != a) return false;
  46   }
  47   return true;
  48 }
  49
  50 int main(){
  51
  52   for (int i=2; i<MAX; i++)
  53     if (!p[i])
  54       for (int j=2*i; j<MAX; j+=i)
  55         p[j] = 1;
  56
  57
  58   int n;
  59   while (scanf("%d", &n) == 1 && n > 0){
  60     if (!p[n] || !c(n)) printf("%d is normal.\n", n);
  61     else{
  62       printf("The number %d is a Carmichael number.\n", n);
  63     }
  64   }
  65   return 0;
  66 }